package 热题100.链表.K个一组翻转链表_25_困难;
import 链表.删除链表的倒数第N个结点_19.Solution.ListNode;
/*
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

思路：
    不能对k取余，有个更简单的办法，用while循环，如果当次循环没有到k就说明结束了
    翻转的代码有所不同，需要对最开始节点head的下一个节点，以及上一轮的head的下一个节点进行更新
    而第一次反转是没有上一轮head节点的，所以需要单独翻转一下
* */
public class Solution {
    public static void main(String[] args) {
        ListNode[] headA = new ListNode[4];
        headA[3] = new ListNode(4,null);
        headA[2] = new ListNode(3,headA[3]);
        headA[1] = new ListNode(2,headA[2]);
        headA[0] = new ListNode(1,headA[1]);
        ListNode ans = reverseKGroup(headA[0], 2);
        while (ans != null){
            System.out.println(ans.val);
            ans = ans.next;
        }
    }
    public static ListNode reverseKGroup(ListNode head, int k) {
        int len = 0;
        ListNode ans = null;
        for (ListNode i = head; i != null; i = i.next){
            // 记录第一个k链表翻转后的头节点
            if (len == k - 1){
                ans = i;
            }
            len ++;
        }
        // 如果一开始就不足k个，就不用反转
        if (len < k){
            return head;
        }
        ListNode start = head;
        len -= k;
        // 先翻转一轮，因为后面都是用的start.next，而start为null就没有next
        start = reverse(start, null, k);
        // 如果大于k就循环翻转
        while (len >= k) {
                len -= k;
                start = reverse(start.next, start, k);
        }
        return ans;
    }

    public static ListNode reverse(ListNode head, ListNode begin,int k){
        ListNode pre = null;
        ListNode cur = head;
        ListNode next;
        int num = k;
        while (num -- > 0){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        head.next = cur;
        // 特殊处理，注意这里和普通的翻转链表不同的地方在于，链表翻转后，最开始节点head的下一个节点，以及上一轮的head的下一个节点要更新
        if (begin != null){
            begin.next = pre;
        }
        return head;
    }
}
